Computer networks have become commonplace and taken many forms, from cellular data networks for smart phones to localized networks such as a Wi-Fi network and the familiar Ethernet connections commonly used to provide hard-wired connection to the Internet. Networks such as these enable users to share resources and data, such as to surf the World Wide Web for information, to send email, or to view a streaming movie.
Information is communicated over the Internet using packet switching technology, in which information is broken up into packets of data that are routed from a source to a destination, typically based on a destination Internet Protocol (IP) address. Routers and other machines in the network use routing protocols to ensure that data makes it from the source machine to the intended destination, which is then able to reassemble the packets to form the original information sent, such as an email, a movie, or a web page.
For example, a user wishing to conduct online banking may open a browser window, such as Internet Explorer or another suitable browser, and enter a Uniform Resource Locator (URL) for the bank's website. The URL is converted to a destination IP address using a domain name server, and the web page request is sent to the bank's servers via the Internet by sending the request through a series of routers which route the request using the destination IP address.
Each router in the network maintains a routing table or other data structure, which includes information regarding the available routes to various network destinations. Routing tables are in some examples static, but in other examples are dynamically updated as a result of a routing protocol discovering information about the network topology around the router. Routing tables often also include metrics such as the distance associated with various routes, such as the number of hops and amount of time needed to communicate with a remote system over a certain network path.
Because routing tables can become large and complex as the size of a network such as the Internet grows, some routers use a forwarding table, which contains forwarding information for only those routes chosen by a routing algorithm for forwarding packets in a network to perform the actual forwarding of data. In such a router, a control plane is often responsible for overseeing management of the router, such as by employing a routing algorithm to maintain a routing table and generate the forwarding table, while a forwarding plane uses the forwarding table to route data packets.
In some cases, many modern routers are not simply a single system with a single control plane and forwarding plane, but are virtual routers which are served by one or more physical routers. In a more detailed example, a virtual router redundancy protocol (VRRP) is often used to specify a router group including a master virtual router, and one or more backup virtual routers on a different physical router operable to take over the master virtual router's routing tasks should the master virtual router fail. However, conventional VRRP protocols do not scale well, and often suffer from lengthy convergence time, i.e., the time required to failover to an elected backup virtual router in the event a master virtual router fails. For example, in router environments such as where many groups of master routers and backup routers are used to provide routing functionality on a smaller number of physical routers, communication of state information throughout the router environment at failover, such as communication of the identity of a backup virtual router that is taking over for a failed master virtual router can become problematic. For example, the associated backup virtual routers consume a significant share of physical router resources and network bandwidth as they broadcast their new roles as master routers to other groups of routers, which may number in the hundreds or thousands.